package LeetCode.month01.day22;

import java.util.*;

public class No869 {
    public static void main(String[] args) {
        System.out.println(reorderedPowerOf2(10));
    }
    static boolean[] visit;
    public static boolean reorderedPowerOf2(int n) {
        char[] chars = Integer.toString(n).toCharArray();
        int len = chars.length;
        Arrays.sort(chars);
        visit = new boolean[len];
        return deepseek(new char[len],0,chars);
    }

    public static boolean deepseek(char[] res,int index,char[] chars){
        if(index==chars.length){
            if(res[0]!='0'){
                int n1 = Integer.parseInt(new String(res));
                if (isPowerOfTwo(n1)) return true;
            }
            return false;
        }
        boolean flag = false;
        for (int i = 0; i < chars.length; i++) {
            if(visit[i]|| (i>0&&!visit[i-1]&&chars[i]==chars[i-1])) continue;
            res[index]=chars[i];
            visit[i]=true;
            if(deepseek(res,index+1,chars)) return true;
            visit[i]=false;
        }
        return false;
    }
    public static boolean isPowerOfTwo(int n){
        return n>0&&((n&n-1)==0);
    }

    static Set<String> set = new HashSet<>();
    public static boolean reorderedPowerOf2Hash(int n) {
        init();
        String s = getchar(n);
        return set.contains(s);
    }

    public static String getchar(int n) {
        char[] res = new char[10];
        while(n>0){
            res[n%10]++;
            n/=10;
        }
        return new String(res);
    }

    public static void init() {
        for (int n = 1;n<1e9;n<<=1){
            set.add(getchar(n));
        }
    }

}
